package backTrack;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
//  CKG TODO 2023/4/22:   首先整体思路搞错了  添加进去的一个path 是aab切割成回文的一种切割方法 这是大前提

public class Class131 {

    List<List<String>> result = new ArrayList<>();
   Deque<String> path  =  new LinkedList<String> ();

    public List<List<String>> partition(String s) {
        backTracking(s,0);
        return  result;
    }

    public void backTracking(String s, int start) {
        if (start>=s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (judgeHuiWen(s,start,i)){
                //  CKG TODO 2023/4/22: 这块还不是特别懂
                String  str=s.substring(start,i+1);
                path.add(str);
            }
            else {
                continue;
            }
            //  CKG TODO 2023/4/22: 还有这个位置
            backTracking(s,i+1);
            path.removeLast();
        }
    }

    public   boolean judgeHuiWen(String s,int left,int right){
        while (left<right){
            if (left<s.length()&&right>=0&&s.charAt(left)==s.charAt(right)){
                left++;
                right--;
            }else {
                return   false;
            }
        }
        return  true;
    }


//    static class Solution {
//        List<List<String>> lists = new ArrayList<>();
//        Deque<String> deque = new LinkedList<>();
//
//        public List<List<String>> partition(String s) {
//            backTracking(s, 0);
//            return lists;
//        }
//
//        private void backTracking(String s, int startIndex) {
//            //如果起始位置大于s的大小，说明找到了一组分割方案
//            if (startIndex >= s.length()) {
//                lists.add(new ArrayList(deque));
//                return;
//            }
//            for (int i = startIndex; i < s.length(); i++) {
//                //如果是回文子串，则记录
//                if (isPalindrome(s, startIndex, i)) {
//                    String str = s.substring(startIndex, i + 1);
//                    deque.addLast(str);
//                } else {
//                    continue;
//                }
//                //起始位置后移，保证不重复
//                backTracking(s, i + 1);
//                deque.removeLast();
//            }
//        }
//        //判断是否是回文串
//        private boolean isPalindrome(String s, int startIndex, int end) {
//            for (int i = startIndex, j = end; i < j; i++, j--) {
//                if (s.charAt(i) != s.charAt(j)) {
//                    return false;
//                }
//            }
//            return true;
//        }
//    }



    public static void main(String[] args) {
        Class131 class131 = new Class131();
//        Solution solution = new Solution();
//
//        System.out.println(solution.partition("aab").toString());
        System.out.println(class131.partition("aab").toString());

    }






}
